package leetcode;

import java.util.Arrays;

public class BuildTree {
    public static void main(String[] args) {
        BuildTree buildTree = new BuildTree();
        int[] preorder = {-1};
        int[] inorder = {-1};
        TreeNode treeNode = buildTree.buildTree(preorder, inorder);
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        int split = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == preorder[0]) {
                split = i;
                break;
            }
        }
        int[] new_inorder_left = splitArray(inorder, 0, split);
        int[] new_inorder_right = splitArray(inorder, split + 1, inorder.length);
        int[] new_preorder_left = splitArray(preorder, 1, new_inorder_left.length + 1);
        int[] new_preorder_right = splitArray(preorder, preorder.length - new_inorder_right.length, preorder.length);
        root.left = buildTree(new_preorder_left, new_inorder_left);
        root.right = buildTree(new_preorder_right, new_inorder_right);
        return root;
    }

    /**
     * 截取子数组
     * [left,right)
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public int[] splitArray(int[] arr, int left, int right) {
        int len = right - left;
        int[] res = new int[len];
        for (int i = left; i < right; i++) {
            res[i - left] = arr[i];
        }
        return res;
    }
}
